Những cư dân đầu tiên của Rwanda ngày nay là người Twa, một nhóm người săn bắn hái lượm, định cư tại đây từ 8000 đến 3000 trước Công nguyên và vẫn ở lại đất nước ngày nay.[1][2] Theo lịch sử truyền miệng, Vương quốc Rwanda được thành lập vào thế kỷ 14 trên bờ hồ Muhazi, cách Kigali ngày nay khoảng 40 km (25 dặm) về phía đông.[3][4][5][6] Vương quốc ban đầu bao gồm Kigali nhưng đó là một nhà nước nhỏ trong lịch sử với các nước láng giềng lớn hơn và hùng mạnh hơn, Bugesera và Gisaka.[7][8] Một thành viên của triều đại Gisaka đã giết vua Ruganzu Bwimba của Rwanda vào thế kỷ 16, nhưng con trai của Ruganzu, Cyirima Rugwe đã chiến đấu trở lại với sự giúp đỡ từ Bugesera và mở rộng lãnh thổ của Rwanda.[9] Vào cuối thế kỷ 16 hoặc đầu thế kỷ 17, vương quốc Rwanda đã bị xâm chiếm từ phía bắc bởi người Banyoro tại Uganda ngày nay.[9] Nhà vua buộc phải chạy trốn về phía tây, để lại Kigali và miền đông Rwanda trong tay Bugesera và Gisaka. Sự hình thành vào thế kỷ 17 của một triều đại Rwanda mới bởi mwami (vua), Ruganzu Ndori, tiếp theo là các cuộc xâm lược về phía đông và cuộc chinh phạt Bugesera, đánh dấu sự khởi đầu của sự thống trị của vương quốc Rwanda trong khu vực.[10] Thủ đô của vương quốc là tại Nyanza, ở phía nam của đất nước.[11]

Thành phố Kigali được thành lập vào năm 1907 bởi nhà thám hiểm người Đức Richard Kandt. Rwanda và nước láng giềng Burundi đã được Hội nghị Berlin năm 1884 giao cho Đức, tạo thành một phần của Đông Phi thuộc Đức, và Đức đã thiết lập sự hiện diện của họ ở nước này vào năm 1897 với việc thành lập liên minh với nhà vua, Yuhi V Musinga. Kandt đến năm 1899, để khám phá Hồ Kivu và tìm kiếm nguồn gốc của sông Nile.[12] Khi Đức quyết định vào năm 1907 để tách chính quyền Rwanda khỏi Burundi, Kandt được chỉ định là cư dân đầu tiên của đất nước.[13] Ông chọn làm trụ sở chính ở Kigali do vị trí trung tâm của nó ở trong nước, và cũng vì địa điểm trên đồi Nyarugenge có tầm nhìn tốt và an ninh. Ngôi nhà của Kandt, nằm gần khu thương mại trung tâm (CBD), là ngôi nhà theo phong cách châu Âu đầu tiên trong thành phố,[14] và ngày nay vẫn được sử dụng làm Bảo tàng Lịch sử Tự nhiên Kandt House.[15] Kandt đã bắt đầu cho phép sự xâm nhập của các thương nhân nước ngoài vào năm 1908, cho phép hoạt động thương mại bắt đầu ở Rwanda. Các doanh nghiệp đầu tiên của Kigali được thành lập bởi các thương nhân Hy Lạp và Ấn Độ, với sự hỗ trợ từ người Baganda và người Swahili.[16] Các mặt hàng được buôn bán bao gồm vải và hạt.[16] Hoạt động thương mại bị hạn chế và chỉ có khoảng 30 công ty trong thành phố vào năm 1914. Kandt cũng mở các trường do chính phủ điều hành ở Kigali, nơi bắt đầu giáo dục những học sinh người Tutsi.[17]

Quân đội Bỉ nắm quyền kiểm soát Rwanda và Burundi trong Thế chiến I, với Kigali bị Lữ đoàn phương Bắc xâm chiếm bởi Đại tá Philippe Molitor vào ngày 6 tháng 5 năm 1916. Đầu năm 1917, Bỉ đã cố gắng khẳng định sự cai trị trực tiếp đối với Rwanda, bắt giữ vua Musinga. Trong thời kỳ này, Kigali là một trong hai thủ đô của tỉnh, cùng với Gisenyi. Tình trạng thiếu lao động nông nghiệp do tuyển dụng người dân địa phương để hỗ trợ quân đội châu Âu trong chiến tranh, cướp bóc lương thực của binh lính và những cơn mưa xối xả phá hủy mùa màng, dẫn đến nạn đói nghiêm trọng khi bắt đầu chính quyền Bỉ. Nạn đói, kết hợp với khó khăn trong việc cai trị xã hội Rwanda phức tạp, đã thúc đẩy người Bỉ thiết lập lại chế độ gián tiếp theo kiểu Đức vào cuối năm 1917. Musinga đã khôi phục lại ngai vàng của mình tại Nyanza, và Kigali vẫn là trung tâm của chính quyền thuộc địa. Sự sắp xếp này vẫn tồn tại cho đến giữa những năm 1920, nhưng từ năm 1924, người Bỉ lại bắt đầu một lần nữa để bên lề chế độ quân chủ, lần này là vĩnh viễn. Bỉ nắm quyền kiểm soát giải quyết tranh chấp, bổ nhiệm các quan chức và thu thuế.[18][19] Kigali vẫn còn tương đối nhỏ trong suốt phần còn lại của thời kỳ thuộc địa, vì phần lớn chính quyền nằm tại thủ đô Bujumbura của Burundi. Dân số của Bujumbura đã vượt quá con số 50.000 trong những năm 1950 và là thành phố duy nhất theo phong cách châu Âu,[20] trong khi dân số của Kigali vẫn ở mức khoảng 6.000 cho đến khi giành được độc lập vào năm 1962.[14]

Kigali trở thành thủ đô của nước Rwanda độc lập vào năm 1962.[21][22] Chính quyền mới đã chọn Kigali vì vị trí của nó ở trung tâm đất nước. Thành phố phát triển ổn định trong những thập kỷ sau; vào đầu những năm 1970, dân số là 25.000 người chỉ với năm con đường trải nhựa và đến năm 1991 là khoảng 250.000.[23] Vào ngày 6 tháng 7 năm 1973, có một cuộc đảo chính quân sự không đổ máu, trong đó bộ trưởng quốc phòng Juvénal Habyarimana đã lật đổ tổng thống cầm quyền Grégoire Kayibanda.[24] Các doanh nghiệp đóng cửa trong vài ngày và quân đội tuần tra khắp thành phố,[25] nhưng sự gián đoạn chỉ diễn ra trong thời gian ngắn và quân đội đã rời khỏi đường phố vào ngày 11 tháng 7.[26]

Thành phố không bị ảnh hưởng trực tiếp trong ba năm đầu của cuộc nội chiến Rwanda năm 1990, mặc dù Mặt trận Ái quốc Rwanda (RPF) đã tiến gần đến việc tấn công thành phố vào tháng 2 năm 1993. Vào tháng 12 cùng năm, sau khi ký kết trong Hiệp định Arusha, một lực lượng gìn giữ hòa bình của Liên Hợp Quốc đã được thành lập trong thành phố và RPF đã được cấp quyền sử dụng một tòa nhà trong thành phố cho các nhà ngoại giao và binh lính của họ. Vào tháng 4 năm 1994, Tổng thống Habyarimana đã bị ám sát khi máy bay của ông bị bắn hạ gần Sân bay quốc tế Kigali. Tổng thống Burundi Cyprien Ntaryamira cũng bị giết trong vụ tấn công.[27] Đây là chất xúc tác cho nạn diệt chủng Rwanda, trong đó 500.000–1.000.000 người Tutsi và người Hutu ôn hòa về mặt chính trị đã bị giết trong các cuộc tấn công được lên kế hoạch kỹ lưỡng theo lệnh của chính phủ lâm thời. Các chính trị gia đối lập ở Kigali đã bị giết vào ngày đầu tiên của cuộc diệt chủng,[28] và thành phố sau đó trở thành bối cảnh chiến đấu ác liệt giữa quân đội và RPF, kể cả tại căn cứ sau này. RPF bắt đầu tấn công từ phía bắc, và dần dần nắm quyền kiểm soát phần lớn đất nước trong khoảng từ tháng 4 đến tháng 6.[29] Sau khi bao vây Kigali và cắt đứt các tuyến đường tiếp tế,[30] họ bắt đầu chiến đấu cho chính thành phố vào giữa tháng Sáu. Các lực lượng chính phủ có nhân lực và vũ khí vượt trội nhưng RPF đã chiến đấu một cách khéo léo và có thể khai thác thực tế là các lực lượng chính phủ đang tập trung vào cuộc diệt chủng thay vì chiến đấu cho Kigali.[31] RPF nắm quyền kiểm soát Kigali vào ngày 4 tháng 7,[32] một ngày hiện được kỷ niệm là ngày lễ quốc khánh.[33]

Kể từ sau chiến tranh và nạn diệt chủng, thành phố đã trải qua sự gia tăng dân số nhanh chóng do di cư từ các khu vực khác, cũng như tỷ lệ sinh cao. Các tòa nhà bị tàn phá nặng nề trong cuộc chiến đã bị phá hủy, phần lớn thành phố đã được xây dựng lại, và các tòa nhà văn phòng và cơ sở hạ tầng hiện đại tồn tại trên toàn thành phố. Một kế hoạch tổng thể, được thành phố và chính phủ thông qua vào năm 2013 và được hỗ trợ bởi tài chính và lao động quốc tế, tìm cách thiết lập Kigali thành một thành phố hiện đại phi tập trung vào năm 2040. Tuy nhiên, sự phát triển đã đi kèm với việc đuổi người dân ở các khu nhà ở không chính thức, và các nhóm như Tổ chức Theo dõi Nhân quyền đã cáo buộc việc chính phủ đưa những người nghèo và trẻ em vào các trung tâm giam giữ.[34][35]